Switchings, extensions, and reductions in central digraphs

A directed graph is called central if its adjacency matrix A satisfies the equation A²=J, where J is the matrix with a 1 in each entry. It has been conjectured that every central directed graph can be obtained from a standard example by a sequence of simple operations called switchings, and also that it can be obtained from a smaller one by an extension. We disprove these conjectures and present a general extension result which, in particular, shows that each counterexample extends to an infinite family.     

Alliance free and alliance cover sets

A defensive (offensive) k-alliance in Γ = (V,E) is a set S ⊆ V such that every υ in S (in the boundary of S) has at least k more neighbors in S than it has in V / S. A set X ⊆ V is defensive (offensive) k-alliance free, if for all defensive (offensive) k-alliance S, S/X ≠ ∅, i.e., X does not contain any defensive (offensive) k-alliance as a subset. A set Y ⊆ V is a defensive (offensive) k-alliance cover, if for all defensive (offensive) k-alliance S, S ∩ Y ≠ ∅, i.e., Y contains at least one vertex from each defensive (offensive) k-alliance of Γ. In this paper we show several mathematical properties of defensive (offensive) k-alliance free sets and defensive (offensive) k-alliance cover sets, including tight bounds on their cardinality.     

平面张弦结构抗连续倒塌的动力分析

杆件由于爆炸、腐蚀等发生脆性破坏后引起剩余结构的振动和压杆由于失稳过程中的弹性突跳（Snap-through）引起的相邻结构振动是张弦结构倒塌过程中常伴生的两种动力现象。本文对第一种动力响应产生的原因、失效构件的模拟方法进行了分析,说明进行张弦结构抗连续倒塌的动力分析应采用初始条件法模拟构件的失效。根据张弦结构的特点,从构件失效和结构失效两方面提出了张弦结构倒塌失效的评估准则,并采用变换荷载路径法通过静力连续倒塌分析找出张弦结构各部分的关键构件;然后采用初始条件法按考虑几何非线性、阻尼比、材料非线性等分别模拟这些关键构件失效引起的动力响应,得到了平面张弦结构各部分构件失效的动力特性、动力放大系数和失效构件的位置,并对不同失效时间进行动力响应分析得到张弦结构动力效应与构件失效时间的关系曲线。最后给出张弦结构进行抗连续倒塌分析的一些结论和建议,如进行连续倒塌动力时程分析时初始失效杆件选取和失效时间取值以及弹性动力放大系数与塑性动力放大系数的区别等,为张弦结构的抗连续倒塌设计提供技术支持和参考。     

Effects of Quantum Nuclear Delocalisation on NMR Parameters from Path Integral Molecular Dynamics

The influence of nuclear delocalisation on NMR chemical shifts in molecular organic solids is explored using path integral molecular dynamics (PIMD) and density functional theory calculations of shielding tensors. Nuclear quantum effects are shown to explain previously observed systematic deviations in correlations between calculated and experimental chemical shifts, with particularly large PIMD‐induced changes (up to 23 ppm) observed for carbon atoms in methyl groups. The PIMD approach also enables isotope substitution effects on chemical shifts and J couplings to be predicted in excellent agreement with experiment for both isolated molecules and molecular crystals. An approach based on convoluting calculated shielding or coupling surfaces with probability distributions of selected bond distances and valence angles obtained from PIMD simulations is used to calculate isotope effects.     

循环图C(10,2)与路P_n的笛卡尔积的交叉数

证明了循环图C(10,2)与路P_n的笛卡尔积的交叉数是10n及循环图C(2m,2)的一点悬挂和两点悬挂的交叉数分别是m,2m.     

Precise Logarithmic Asymptotics for the Right Tails of Some Limit Random Variables for Random Trees

For certain random variables that arise as limits of functionals of random finite trees, we obtain precise asymptotics for the logarithm of the right-hand tail. Our results are based on the facts (i) that the random variables we study can be represented as functionals of a Brownian excursion and (ii) that a large deviation principle with good rate function is known explicitly for Brownian excursion. Examples include limit distributions of the total path length and of the Wiener index in conditioned Galton-Watson trees (also known as simply generated trees). In the case of Wiener index (where we recover results proved by Svante Janson and Philippe Chassaing by a different method) and for some other examples, a key constant is expressed as the solution to a certain optimization problem, but the constant’s precise value remains unknown. Research supported by NSF grants DMS-0104167 and DMS-0406104 and by The Johns Hopkins University’s Acheson J. Duncan Fund for the Advancement of Research in Statistics.     

A fuzzy shortest path with the highest reliability

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.     

An extension of labeling techniques for finding shortest path trees

Label setting techniques are all based on Dijkstra’s condition of always scanning the node with the minimum label, which guarantees that each node will be scanned exactly once; while this condition is sufficient it is not necessary. In this paper, we discuss less restrictive conditions that allow the scanning of a node that does not have the minimum label, yet still maintaining sufficiency in scanning each node exactly once; various potential shortest path schemes are discussed, based on these conditions. Two approaches, a label setting and a flexible hybrid one are designed and implemented. The performance of the algorithms is assessed both theoretically and computationally. For comparative analysis purposes, three additional shortest path algorithms – the commonly cited in the literature – are coded and tested. The results indicate that the approaches that rely on the less restrictive optimality conditions perform substantially better for a wide range of network topologies.     

Finding Shortest Paths in a Sequence of Triangles in 3D by the Planar Unfolding

We present an efficient algorithm for finding the shortest path joining two points in a sequence of triangles in three-dimensional space using the concept of funnels associated with common edges along the sequence of triangles and the planar unfolding for each funnel. We show that the unfolded image of a funnel is a simple polygon, it thus is non-overlapping. Therefore, such funnels are determined iteratively to their associated common edges by the planar unfolding and the shortest path joining two points is determined by cusps of these funnels.